package Top200;

import java.util.Stack;

/**
 * @author zhangmin
 * @create 2022-02-26 14:17
 * 单调栈，从左到右记录第一个比i小的左边的元素，从右到左记录第一个比i小的右侧位置，left[i],right[i]之间i的高度是最低。
 */
public class largestRectangleArea84 {
    public int largestRectangleArea(int[] heights) {
        int n= heights.length;
        int[] left=new int[n],right=new int[n];
        Stack<Integer> stack=new Stack<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                stack.pop();
            }
            left[i]=stack.isEmpty()?-1:stack.peek();
            stack.push(i);
        }
        stack.clear();
        for (int i = n-1; i >= 0; i--) {
            while (!stack.isEmpty()&&heights[stack.peek()]>=heights[i]){
                stack.pop();
            }
            right[i]=stack.isEmpty()?n:stack.peek();
            stack.push(i);
        }
        int res=0;
        for (int i = 0; i < n; i++) {
            res=Math.max(res,(right[i]-left[i]-1)*heights[i]);
        }
        return res;
    }
}
